package com.LeeCode;

/**
 * 两个非重叠子数组的最大和
 */

public class Code1031 {
    public static void main(String[] args) {
        int[] nums = {0, 6, 5, 2, 2, 5, 1, 9, 4};
        int firstLen = 1, secondLen = 2;
        System.out.println(new Code1031().maxSumTwoNoOverlap(nums, firstLen, secondLen));
    }

    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        // 计算前缀和
        for (int i = 1; i < nums.length; i++) {
            nums[i] += nums[i - 1];
        }

        // 两种情况取最大值
        return Math.max(helper(nums, firstLen, secondLen), helper(nums, secondLen, firstLen));
    }

    private int helper(int[] nums, int L, int M) {
        int res = nums[L + M - 1];           // 初始结果
        int maxL = nums[L - 1];              // L长度子数组的最大和

        // 从 L+M 位置开始遍历
        for (int i = L + M; i < nums.length; i++) {
            // 更新L长度子数组的最大和
            maxL = Math.max(maxL, nums[i - M] - nums[i - M - L]);

            // 更新最终结果
            res = Math.max(res, maxL + (nums[i] - nums[i - M]));
        }
        return res;
    }
}
